GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Graph (Graphentheorie)</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Graph (Graphentheorie)</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Ein Graph ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. Die mathematischen Abstraktionen der Objekte werden dabei <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> (auch Ecken) des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> (manchmal auch Bögen). Die Kanten können <a href="Kante_(Graphentheorie)#Kantenarten_und_ihre_Notation" title="Kante (Graphentheorie)">gerichtet</a> oder <a href="Kante_(Graphentheorie)#Kantenarten_und_ihre_Notation" title="Kante (Graphentheorie)">ungerichtet</a> sein. Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.<a href="#cite_note-Diestel2010-1">[1]</a>

In einem U-Bahn-Netz stellt jeder Knoten eine U-Bahn-Station dar und jede Kante eine direkte Zugverbindung zwischen zwei Stationen. Die <a href="Chemische_Graphentheorie" title="Chemische Graphentheorie">chemische Graphentheorie</a> betrachtet <a href="Molek%C3%BCl" title="Molekül">Moleküle</a> als Graphen, mit Atomen als Knoten und <a href="Molekularverbindung" class="mw-redirect" title="Molekularverbindung">Molekularverbindungen</a> als Kanten. Komplexe räumliche Gebilde wie <a href="Polyeder" title="Polyeder">Polyeder</a> können als Graphen dargestellt werden (<a href="Schlegeldiagramm" title="Schlegeldiagramm">Schlegeldiagramm</a>). Das <a href="Internet" title="Internet">Internet</a> ist ein riesiger Graph aus <a href="Computer" title="Computer">Computern</a> und <a href="Datenverbindung" class="mw-redirect" title="Datenverbindung">Datenverbindungen</a>.

<a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Bäume</a> wie etwa <a href="Stammbaum" title="Stammbaum">Stammbäume</a> sind ein Sonderfall der Graphen und enthalten keine <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklen</a>.

Die mathematische Betrachtung von Graphen begann im 18. Jahrhundert mit dem <a href="K%C3%B6nigsberger_Br%C3%BCckenproblem" title="Königsberger Brückenproblem">Königsberger Brückenproblem</a>.

<div class="mw-heading mw-heading2"><h2 id="Typen_von_Graphen">Typen von Graphen</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Ungerichteter_Graph">Ungerichteter Graph</h3></div>

In ungerichteten Graphen werden die Verbindungen zwischen <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> durch <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> gekennzeichnet. Die Kanten haben keine Richtung. Jede Kante kann in beide Richtungen durchlaufen werden.

<div class="mw-heading mw-heading3"><h3 id="Gerichteter_Graph_(Digraph)">Gerichteter Graph (Digraph)</h3></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Gerichteter_Graph" title="Gerichteter Graph">Gerichteter Graph</a></div>

In Digraphen (von englisch directed graph, auch gerichtete Graphen genannt) werden Kanten statt durch Linien durch Pfeile gekennzeichnet, wobei der Pfeil von ihrem Anfangs- zu ihrem Endknoten zeigt. Dies verdeutlicht, dass jede Kante des Graphen nur in eine Richtung durchlaufen werden kann.<a href="#cite_note-2">[2]</a> Ein Spezialfall davon sind orientierte Graphen, in denen es keine ungerichteten Kanten gibt, d. h. gibt es eine Kante von Knoten A nach B, dann gibt es nie auch die umgekehrte Kante von B nach A.

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baum (Graphentheorie)</a></div>

Ein <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baum</a> ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein spezieller Typ von Graph, der zusammenhängend ist und keine geschlossenen <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Pfade</a>, also <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklen</a> der Länge größer oder gleich 3, enthält. Bei allen Bäumen ist die Anzahl der Knoten offensichtlich um 1 größer als die Anzahl der Kanten.

Bäume haben sehr viele praktische Anwendungen, vor allem in der <a href="Informatik" title="Informatik">Informatik</a>. Viele <a href="Algorithmus" title="Algorithmus">Algorithmen</a> werden mithilfe von Bäumen <a href="Programmierung" title="Programmierung">programmiert</a>. Zum Beispiel können <a href="Netzwerk" title="Netzwerk">Netzwerke</a>, <a href="Verkehrsnetz" title="Verkehrsnetz">Verkehrsnetze</a> oder <a href="Versorgungsnetz" class="mw-redirect" title="Versorgungsnetz">Versorgungsnetze</a> mit einer <a href="Breitensuche" title="Breitensuche">Breitensuche</a> oder einer <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> effektiv durchlaufen werden. Im Bereich der <a href="K%C3%BCnstliche_Intelligenz" title="Künstliche Intelligenz">künstlichen Intelligenz</a> und der <a href="Strategiespiel" title="Strategiespiel">Strategiespiele</a> ist die <a href="Alpha-Beta-Suche" title="Alpha-Beta-Suche">Alpha-Beta-Suche</a> wichtig. Sie basiert auf <a href="Suchbaum" title="Suchbaum">Suchbäumen</a>.

<div class="mw-heading mw-heading3"><h3 id="Multigraph">Multigraph</h3></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Multigraph" title="Multigraph">Multigraph</a></div>

In Multigraphen können zwei Knoten durch mehrere Kanten<a href="#cite_note-MultDirected-3">[3]</a> verbunden sein, was in <a href="Einfacher_Graph" title="Einfacher Graph">einfachen Graphen</a> nicht erlaubt ist. Außerdem dürfen Multigraphen Schleifen enthalten: Kanten, die zum selben Knoten führen, von dem sie ausgehen.<a href="#cite_note-Diestel2010-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Planarer_Graph">Planarer Graph</h3></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Planarer_Graph" title="Planarer Graph">Planarer Graph</a></div>

Ein <a href="Planarer_Graph" title="Planarer Graph">planarer Graph</a> ist ein Graph, der auf einer Ebene, mit Punkten für die <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> und Linien für die <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a>, dargestellt werden kann, sodass sich keine Kanten schneiden. Jeder planare Graph hat einen <a href="Dualit%C3%A4t_(Mathematik)#Geometrisch_dualer_Graph" title="Dualität (Mathematik)">dualen Graphen</a>. Das ist ein Graph, wo jeder Fläche des Graphen ein <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> zugeordnet ist, der innerhalb dieser Fläche liegt, und umgekehrt. Die Dualität von planaren Graphen ist immer gegenseitig, das heißt, der duale Graph des dualen Graphen jedes planaren Graphen ist der ursprüngliche planare Graph.

Für planare Graphen gilt der <a href="Eulerscher_Polyedersatz" title="Eulerscher Polyedersatz">Eulersche Polyedersatz</a>, der oft mit der <a href="Gleichung" title="Gleichung">Gleichung</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E-K+F=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E-K+F=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cb03178214f455b9edc0b70742cc278ba7620410.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.524ex; height:2.343ex;" alt="{\displaystyle E-K+F=2}" loading="lazy"> dargestellt wird.

<div class="mw-heading mw-heading3"><h3 id="Hypergraph">Hypergraph</h3></div>

Bei Hypergraphen verbindet eine Kante (auch Hyperkante genannt) nicht nur zwei, sondern mehrere Knoten gleichzeitig. Hypergraphen können beispielsweise durch mehrere <a href="Planarer_Graph" title="Planarer Graph">planare Graphen</a> mit <a href="Index_(Mathematik)" class="mw-redirect" title="Index (Mathematik)">Indizierung</a> der Kanten dargestellt werden. Hypergraphen mit wenigen Kanten (sogenannte dünne Graphen) zeichnet man so, dass man eine Menge von Punkten zeichnet, die den Knoten entsprechen, und die zu einer Hyperkante gehörigen Punkte werden dann durch eine geschlossene Linie umkreist, die somit die <a href="Teilmenge" title="Teilmenge">Teilmenge</a> der zu ihr gehörenden Knoten innerhalb aller Knoten angibt. Bei Hypergraphen mit vielen Kanten wird diese Darstellung aber schnell unübersichtlich. Weniger intuitiv, aber übersichtlicher ist es dann, einen Hypergraphen als <a href="Bipartit" class="mw-redirect" title="Bipartit">bipartiten</a> Meta-Graphen darzustellen, wobei die eine der beiden Bipartitionsmengen den Knoten des Hypergraphen, die andere Bipartitionsmenge den Hyperkanten des Hypergraphen entspricht. Die Kanten zwischen diesen beiden Bipartitionsmengen symbolisieren dann die Zugehörigkeit der Knoten zu den Hyperkanten.

Das Physik-Projekt von <a href="Stephen_Wolfram" title="Stephen Wolfram">Stephen Wolfram</a> (siehe auch: <a href="Wolfram_Research" title="Wolfram Research">Wolfram Research</a> und <a href="Mathematica" title="Mathematica">Mathematica</a>) zur Erklärung der Grundlagen der Physik basiert unter anderem auf dem Raum der Regeln über Hypergraphen: „Und zumindest in einer gewissen Annäherung können wir dann sagen, dass Energie mit der Aktivität im Hypergraphen, die Information durch die Zeit fortpflanzt, assoziiert ist, während Impuls mit Aktivität assoziiert ist, die Information im Raum fortpflanzt.“<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

Ein Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ist ein <a href="Geordnetes_Paar" title="Geordnetes Paar">geordnetes Paar</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01724c7d662052bd5f1c34cb725c8001634069a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.406ex; height:2.843ex;" alt="{\displaystyle (V,E)}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> eine <a href="Mengenlehre" title="Mengenlehre">Menge</a> von Knoten (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> vertex/vertices, oft auch Ecken genannt) und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> eine Menge von Kanten (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> edge/edges, manchmal auch Bögen genannt) bezeichnet. Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> in

<ul><li>ungerichteten Graphen ohne Mehrfachkanten eine <a href="Teilmenge" title="Teilmenge">Teilmenge</a> aller 2-elementigen Teilmengen von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"><a href="#cite_note-Diestel2010-1">[1]</a>,</li>

<li><a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten Graphen</a> ohne Mehrfachkanten eine Teilmenge des <a href="Kartesisches_Produkt" title="Kartesisches Produkt">kartesischen Produkts</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V\times V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V\times V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55115711e4cc81797cf763ed90fc991a306523e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.415ex; height:2.176ex;" alt="{\displaystyle V\times V}" loading="lazy">,<a href="#cite_note-5">[5]</a></li>

<li>ungerichteten Graphen mit zusammengefassten Mehrfachkanten eine <a href="Multimenge" title="Multimenge">Multimenge</a> über der Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"> aller 2-elementigen Teilmengen von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy">, also eine <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Funktion</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E\colon W\to \mathbb {N} _{0}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E\colon W\to \mathbb {N} _{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0e9a4666fa2168478f78313f89b6ff439b7d6076.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.591ex; height:2.509ex;" alt="{\displaystyle E\colon W\to \mathbb {N} _{0}}" loading="lazy">,</li>

<li>gerichteten Graphen mit zusammengefassten Mehrfachkanten eine Multimenge über dem kartesischen Produkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V\times V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V\times V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55115711e4cc81797cf763ed90fc991a306523e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.415ex; height:2.176ex;" alt="{\displaystyle V\times V}" loading="lazy">, also eine Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E\colon V\times V\to \mathbb {N} _{0}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E\colon V\times V\to \mathbb {N} _{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c79b68d4a4973591b84c9774a6b749417ed5b06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.571ex; height:2.509ex;" alt="{\displaystyle E\colon V\times V\to \mathbb {N} _{0}}" loading="lazy">,</li>

<li>gerichteten Graphen mit eigenständigen Mehrfachkanten eine beliebige Menge, deren Elemente mit Hilfe von zwei Funktionen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {src} ,\mathrm {tgt} \colon E\to V}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {src} ,\mathrm {tgt} \colon E\to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8cab9dc70c42922864e60ca436d95d09a6ce2af2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.077ex; height:2.509ex;" alt="{\displaystyle \mathrm {src} ,\mathrm {tgt} \colon E\to V}" loading="lazy">, die den Elementen einen Quell- bzw. Zielknoten zuordnen, als Kanten angesehen werden (so ein Graph ist dasselbe wie ein <a href="Funktor_(Mathematik)" title="Funktor (Mathematik)">Funktor</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G\colon {\mathcal {G}}\to \mathbf {Set} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G\colon {\mathcal {G}}\to \mathbf {Set} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b72635d9c7a7c0c62dfdcb3fdd466a98bbf1bb8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.617ex; height:2.343ex;" alt="{\displaystyle G\colon {\mathcal {G}}\to \mathbf {Set} }" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a980c59d42c003fd07fdf3646e1fb95ff82f99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.392ex; height:2.343ex;" alt="{\displaystyle {\mathcal {G}}}" loading="lazy"> die recht überschaubare Kategorie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}=\{V{\stackrel {\mathrm {src} }{\longleftarrow }}E{\stackrel {\mathrm {tgt} }{\longrightarrow }}V\}}">

</mrow>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}=\{V{\stackrel {\mathrm {src} }{\longleftarrow }}E{\stackrel {\mathrm {tgt} }{\longrightarrow }}V\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8e9a1d3a8cf55ab793a39950eb897f301ce8ddd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.71ex; height:4.176ex;" alt="{\displaystyle {\mathcal {G}}=\{V{\stackrel {\mathrm {src} }{\longleftarrow }}E{\stackrel {\mathrm {tgt} }{\longrightarrow }}V\}}" loading="lazy"> mit zwei Objekten und zwei ausgezeichneten Pfeilen ist)</li>

<li>Hypergraphen eine Teilmenge der <a href="Potenzmenge" title="Potenzmenge">Potenzmenge</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy">.<a href="#cite_note-Diestel2010-1">[1]</a></li></ul>

<table>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td></tr></tbody></table>

Den Zusatz „ohne Mehrfachkanten“ lässt man gewöhnlich weg und nennt Graphen mit Mehrfachkanten Multigraphen. Ferner verzichtet man meist auf das Attribut „ungerichtet“ und kennzeichnet nur gerichtete Graphen explizit. Ungerichtete Graphen ohne Mehrfachkanten nennt man auch häufig schlicht oder einfach. Eine andere Bezeichnung für gerichtete Graphen ist Digraph (Directed Graph).

<div class="mw-heading mw-heading3"><h3 id="Abgeleitete_Bezeichnungen">Abgeleitete Bezeichnungen</h3></div>

Statt die Knoten- und Kantenmenge eines Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> mit den Symbolen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> zu identifizieren, kann man auch allgemeine <a href="Abbildung_(Mathematik)" class="mw-redirect" title="Abbildung (Mathematik)">Abbildungen</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> definieren, die einen Graphen auf dessen Knotenmenge oder Kantenmenge abbilden. Für zwei Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=(V_{1},E_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=(V_{1},E_{1})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce54faeead4cd211047907a335458e7dc8306daf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{1}=(V_{1},E_{1})}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=(V_{2},E_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=(V_{2},E_{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2e832bb526bf16909e2e39f7332a036103557d1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{2}=(V_{2},E_{2})}" loading="lazy"> bezeichnen also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(G_{1}):=V_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(G_{1}):=V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bd0d9df0783c70c2f2245cf47ef85bb06e1bb689.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.632ex; height:2.843ex;" alt="{\displaystyle V(G_{1}):=V_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(G_{1}):=E_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(G_{1}):=E_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9f32081c9918d5f8bf16081a4538d4468cf690fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.981ex; height:2.843ex;" alt="{\displaystyle E(G_{1}):=E_{1}}" loading="lazy"> sowie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(G_{2})=V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(G_{2})=V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f1634afd6e391494a41306862bd08f222ba1a5d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.985ex; height:2.843ex;" alt="{\displaystyle V(G_{2})=V_{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(G_{2})=E_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(G_{2})=E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81850f7ac8b2caf1ef0cf67ecce75bd4e72f9454.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.334ex; height:2.843ex;" alt="{\displaystyle E(G_{2})=E_{2}}" loading="lazy">.

Die Mehrdeutigkeit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(G)=V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(G)=V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6b0d6218fff612255009cc8cbb63bd48bb450ab9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.309ex; height:2.843ex;" alt="{\displaystyle V(G)=V}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(G)=E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(G)=E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9a3bc9232cf173f0ceb1e54766c5e482dd7cf132.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.286ex; height:2.843ex;" alt="{\displaystyle E(G)=E}" loading="lazy"> wird bei dieser Notation in Kauf genommen, obwohl die Abbildungen etwas anderes darstellen als die mit ihr verbundene Knoten- und Kantenmenge. Als Konvention bietet sich an, mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> ohne <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Argument</a> Knoten- bzw. Kantenmenge zu bezeichnen, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> mit Argument bezeichnen dagegen die definierten Abbildungen.

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ein Graph, so sagt man allgemein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> ist Knoten bzw. Ecke von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ba39dee5fd7f4467e387af4026315fb1fb21628.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.423ex; height:2.843ex;" alt="{\displaystyle V(G)}" loading="lazy"> gehört. Außerdem bezeichnet man Kanten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E(G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dcbe07e4cf5a71281984b081acaff2f4749f0856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.336ex; height:2.843ex;" alt="{\displaystyle e\in E(G)}" loading="lazy"> als

<ul><li>ungerichtete Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ein ungerichteter Graph ist.</li>

<li>gerichtete Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ein gerichteter Graph ist.</li>

<li>Hyperkante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ein Hypergraph ist.</li></ul>

In einer ungerichteten Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e=\lbrace v,w\rbrace }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e=\lbrace v,w\rbrace }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b25f9aa2090e14dbda4a88e0fd5fcf0d01e56d63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.333ex; height:2.843ex;" alt="{\displaystyle e=\lbrace v,w\rbrace }" loading="lazy"> bezeichnet man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> als Endknoten von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">. In einer gerichteten Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e=(v,w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e=(v,w)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4c44f467603bbe85d35f31ae56985ec911a67f3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.817ex; height:2.843ex;" alt="{\displaystyle e=(v,w)}" loading="lazy"> bezeichnet man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> als Startknoten und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> als Endknoten von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">.

Bei Multigraphen bezeichnet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(G)(e)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(G)(e)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75472404fa960565f9ead94f201714dd9262d211.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.304ex; height:2.843ex;" alt="{\displaystyle E(G)(e)}" loading="lazy"> die Vielfachheit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">. Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(G)(e)>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(G)(e)>1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/23469fb33277d097f3990bd7a2879810fee36963.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.565ex; height:2.843ex;" alt="{\displaystyle E(G)(e)>1}" loading="lazy"> gilt, so spricht man von einer Multi- oder Mehrfachkante.

Hat eine Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy"> in gerichteten Graphen die Form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (v,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (v,v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d2f7d731b2097f85e727cafd518a6819d8a115bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.098ex; height:2.843ex;" alt="{\displaystyle (v,v)}" loading="lazy">, so spricht man von einer Schleife. Ist die Schleife <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy"> in einem Multigraphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> zugleich eine Mehrfachkante, so spricht man von einer Mehrfachschleife. Gerichtete Graphen ohne Schleifen nennt man schleifenlos oder schleifenfrei.

Als Knotenzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n(G)=\vert V(G)\vert }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n(G)=\vert V(G)\vert }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9332167dcecdf475dbc5da408151e7dd7abc9928.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.846ex; height:2.843ex;" alt="{\displaystyle n(G)=\vert V(G)\vert }" loading="lazy"> eines Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> bezeichnet man die Anzahl seiner Knoten, als Kantenzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m(G)=\vert E(G)\vert }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m(G)=\vert E(G)\vert }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2fe76a87cfff60e52f9b55dc177d0a85fc028b84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.48ex; height:2.843ex;" alt="{\displaystyle m(G)=\vert E(G)\vert }" loading="lazy"> bezeichnet man die Anzahl seiner Kanten (in Multigraphen summiert man über die Vielfachheit der Kanten).

Zwei Knoten heißen benachbart, wenn eine Kante sie verbindet.

<div class="mw-heading mw-heading3"><h3 id="Spezialfälle">Spezialfälle</h3></div>

Verbindet in einem gerichteten Graphen die Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e81caf3d4bcb929315801cbabc83543829484ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.138ex; height:2.009ex;" alt="{\displaystyle e_{1}}" loading="lazy"> zwei Knoten, und die Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4045b5c7cee9bd0681153bbb077489b13269355e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.138ex; height:2.009ex;" alt="{\displaystyle e_{2}}" loading="lazy"> dieselben Knoten in umgekehrter Richtung, kann man beide zusammen auch als eine ungerichtete Kante innerhalb des gerichteten Graphen betrachten. Im Falle von Mehrfachkanten müssen die Vielfachheiten beider Kanten übereinstimmen.

Gibt es zu jeder Kante eines gerichteten Graphen eine solche entgegengesetzte Kante im Graphen, so ist er ein symmetrischer Graph.

Einen Graphen, dessen Knotenmenge endlich ist, nennt man einen endlichen Graphen. Im Gegensatz dazu nennt man einen Graphen, dessen Knotenmenge unendlich ist, <a href="Unendlicher_Graph" title="Unendlicher Graph">unendlichen Graphen</a>. Meist betrachtet man nur endliche Graphen und lässt daher das Attribut „endlich“ weg, während man unendliche Graphen explizit kennzeichnet.

<div class="mw-heading mw-heading4"><h4 id="Teilgraphen,_Wege_und_Zyklen">Teilgraphen, Wege und Zyklen </h4></div>

Ein <a href="Teilgraph" title="Teilgraph">Teilgraph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy"> eines Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> enthält nur Knoten und Kanten, die auch in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> enthalten sind. Ein von einer Knotenmenge U <a href="Induzierter_Teilgraph" class="mw-redirect" title="Induzierter Teilgraph">induzierter Teilgraph</a> enthält die Knoten aus U und alle Kanten aus G zwischen diesen Knoten.

Eine Folge von paarweise verschiedenen Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1},\ldots ,v_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{1},\ldots ,v_{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb40a91abab8b7bfb0e84b074732b2f044fd56ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.706ex; height:2.009ex;" alt="{\displaystyle v_{1},\ldots ,v_{n}}" loading="lazy">, in der aufeinander folgende Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i+1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fda426c85b6383ebcbde4676a5237b2f646d66c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.028ex; height:2.009ex;" alt="{\displaystyle v_{i+1}}" loading="lazy"> im Graphen durch eine Kante verbunden sind, bezeichnet man als <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Weg</a>, manchmal auch als Pfad. Gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1}=v_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{1}=v_{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/12fe46f9198ed54584c9d0d8ff6c1cefb8a2a621.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.626ex; height:2.009ex;" alt="{\displaystyle v_{1}=v_{n}}" loading="lazy">, und ist dies der einzige doppelte Knoten, spricht man von einem <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklus</a> oder Kreis. Eine Sequenz von benachbarten Knoten, in der sich Knoten wiederholen dürfen, bezeichnet man als <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Kantenfolge</a>. Die Begriffe Weg, Pfad, Kantenfolge, Kreis und Zyklus werden in der Literatur zum Teil unterschiedlich definiert.

Enthält ein gerichteter Graph keinen Zyklus, nennt man ihn azyklisch oder zyklenfrei – also einen gerichteten azyklischen Graphen (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> DAG, directed acyclic graph). Ein solcher Graph lässt sich durch die Ergänzung aller Kanten, die gleichen Ausgangs- und Endknoten wie <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Wege</a> haben, also die Umwege über andere Kanten zu einem Zielknoten abkürzen, zu einer (endlichen und diskreten) <a href="Halbordnung" class="mw-redirect" title="Halbordnung">Halbordnung</a> erweitern. Diesen Vorgang nennt man die Bildung der <a href="Transitive_H%C3%BClle_(Relation)" title="Transitive Hülle (Relation)">transitiven Hülle</a>. Ein <a href="Hasse-Diagramm" title="Hasse-Diagramm">Hasse-Diagramm</a> ist ein gerichteter azyklischer Graph, bei dem die durch das <a href="Transitive_Relation" title="Transitive Relation">Transitivitätsgesetz</a> implizierten Kanten weggelassen sind (<a href="Transitive_H%C3%BClle_(Relation)#Transitive_Reduktion" title="Transitive Hülle (Relation)">transitive Reduktion</a>).

<div class="mw-heading mw-heading2"><h2 id="Grundlegende_Operationen">Grundlegende Operationen</h2></div>

Bei der Untersuchung von Grapheneigenschaften kommt es häufiger vor, dass man auf Graphen einfache Operationen anwenden muss, um möglichst kompakt und damit leichter verständlich schreiben zu können. Besonders häufig werden die üblichen Operationen der Mengenlehre (Vereinigung, Durchschnitt, Differenz und Komplement) auf Knoten- bzw. Kantenmengen von Graphen angewendet, sodass diese direkt auf Graphen definiert werden.

Sind <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=(V_{1},E_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=(V_{1},E_{1})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce54faeead4cd211047907a335458e7dc8306daf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{1}=(V_{1},E_{1})}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=(V_{2},E_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=(V_{2},E_{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2e832bb526bf16909e2e39f7332a036103557d1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{2}=(V_{2},E_{2})}" loading="lazy"> Graphen desselben <a href="Typen_von_Graphen_in_der_Graphentheorie" class="mw-redirect" title="Typen von Graphen in der Graphentheorie">Typs</a>, so bezeichnet

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}+G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/12b0ac4ef31b9391c6d0807d3a844dd10ec5e5e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.602ex; height:2.509ex;" alt="{\displaystyle G_{1}+G_{2}}" loading="lazy"> den Graphen, der entsteht, wenn man die Knoten- und Kantenmenge vereinigt,</li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}-E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d2bc1582167a4e37a9a7998482935517987b0d61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.491ex; height:2.509ex;" alt="{\displaystyle G_{1}-E_{2}}" loading="lazy"> den Graphen, der entsteht, wenn man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e6ee346e54f38302f47b5cf3016d8718f2040c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle E_{2}}" loading="lazy"> von der Kantenmenge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> abzieht und</li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}-V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffec51e171b31920dd72be30050e36807b6fbb19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.131ex; height:2.509ex;" alt="{\displaystyle G_{1}-V_{2}}" loading="lazy"> den Graphen, der entsteht, wenn man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ceaa689a894f5020a7b46177d201cbce2d41122b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{2}}" loading="lazy"> von der Knotenmenge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> abzieht und alle Kanten entfernt, die Knoten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ceaa689a894f5020a7b46177d201cbce2d41122b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{2}}" loading="lazy"> enthalten.</li></ul>

Man beachte dabei die unterschiedliche Definition der Begriffe Vereinigungsmenge und <a href="Differenzmenge" class="mw-redirect" title="Differenzmenge">Differenzmenge</a> für <a href="Menge_(Mathematik)" title="Menge (Mathematik)">Mengen</a> und <a href="Multimenge" title="Multimenge">Multimengen</a>. Man schreibt auch abkürzend

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}+E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/64e16baedc843707e6d4d3639467eec5879bd074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.491ex; height:2.509ex;" alt="{\displaystyle G_{1}+E_{2}}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ceaa689a894f5020a7b46177d201cbce2d41122b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{2}}" loading="lazy"> Teilmenge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adfdbc929f16cb00bb43289c223651b41f7b9f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{1}}" loading="lazy"> ist,</li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}+V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99dbbee60aa73c05c80a0d8c6200807d572222cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.131ex; height:2.509ex;" alt="{\displaystyle G_{1}+V_{2}}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e6ee346e54f38302f47b5cf3016d8718f2040c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle E_{2}}" loading="lazy"> leer oder Teilmenge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7ac42446bcd2cbb76ec8fe2895635d328da22e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle E_{1}}" loading="lazy"> ist,</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}+\{v,w\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4105f1a3c38ab5c06cab505ea862f99bb10e70b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.872ex; height:2.843ex;" alt="{\displaystyle G_{1}+\{v,w\}}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=(\{v,w\},\{\{v,w\}\})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=(\{v,w\},\{\{v,w\}\})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af064a2a47b7c39e66d03a5832ce0e29f77c55f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.449ex; height:2.843ex;" alt="{\displaystyle G_{2}=(\{v,w\},\{\{v,w\}\})}" loading="lazy">,</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}+v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/35fdcbec03f45b29078ac29000cb4a2d4ad2b548.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.849ex; height:2.509ex;" alt="{\displaystyle G_{1}+v}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=(\{v\},\{\})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=(\{v\},\{\})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/450acbbb419f4b76d55cfef11d36094458174df7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.6ex; height:2.843ex;" alt="{\displaystyle G_{2}=(\{v\},\{\})}" loading="lazy">,</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}-\{v,w\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/51ce91b11ca83e1faab536990ae606d4097f1472.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.872ex; height:2.843ex;" alt="{\displaystyle G_{1}-\{v,w\}}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{2}=\{\{v,w\}\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{2}=\{\{v,w\}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b8698a0f05fc73f2692515ac52c4b578a1f3dc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.343ex; height:2.843ex;" alt="{\displaystyle E_{2}=\{\{v,w\}\}}" loading="lazy"> und</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}-v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/05da860544ff979edadd2897a18f0d3875f110ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.849ex; height:2.509ex;" alt="{\displaystyle G_{1}-v}" loading="lazy"> falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{2}=\{v\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{2}=\{v\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b704268805ab876ccc5f74b4eda52f2e6c30fbe7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.96ex; height:2.843ex;" alt="{\displaystyle V_{2}=\{v\}}" loading="lazy">.</li></ul>

<a href="Kantenkontraktion" title="Kantenkontraktion">Kantenkontraktion</a> und die Bildung des <a href="Komplementgraph" title="Komplementgraph">Komplementgraphen</a> sind weitere Basisoperationen.

<div class="mw-heading mw-heading2"><h2 id="Bemerkungen">Bemerkungen</h2></div>

Ungerichtete Graphen ohne Mehrfachkanten sind Spezialfälle von Hypergraphen.

Multigraphen, in denen keine Mehrfachkanten vorkommen, sind zwar nicht formal, aber anschaulich äquivalent zu Graphen ohne Mehrfachkanten, weshalb man auch diese als Graphen ohne Mehrfachkanten bezeichnet. Es gibt eine bijektive Zuordnung zwischen den beiden Varianten.

In diesem Sinne sind Graphen ohne Mehrfachkanten also Spezialfälle von Graphen mit Mehrfachkanten. Ähnlich verhält es sich mit ungerichteten Graphen, die in gewissem Sinn Spezialfälle von gerichteten Graphen sind. Ist ein gerichteter Graph symmetrisch und schleifenlos, so bezeichnet man diesen auch als ungerichtet, da es auch hier eine einfache eineindeutige Zuordnung zwischen beiden Varianten gibt (siehe auch <a href="Adjazenzmatrix" title="Adjazenzmatrix">Adjazenzmatrix</a>).

Es lassen sich natürlich auch ungerichtete Graphen mit Schleifen definieren, wobei man diese wohl am einfachsten wie eben als (formale) Spezialfälle von gerichteten Graphen definiert und die Bedingung der Schleifenlosigkeit weg lässt. Solche Graphen sind aber nur selten Gegenstand der Betrachtungen in der Graphentheorie.

Der wohl allgemeinste Typ von Graphen sind gerichtete <a href="Hypergraph" class="mw-redirect" title="Hypergraph">Hypergraphen</a> mit Mehrfachkanten. Jeder oben definierte Graphentyp kann dann als Spezialfall von diesem betrachtet werden. Solche Graphen sind aber so gut wie gar nicht Gegenstand der Betrachtungen in der Graphentheorie, weshalb sie hier auch nicht näher erläutert werden.

Sollen Graphen als Darstellung eines Sachverhaltes herhalten, werden Algorithmen benötigt, die für das <a href="Graphzeichnen" title="Graphzeichnen">Graphzeichnen</a> benötigt werden. Diese Disziplin der Informatik hat sich in den letzten Jahren stets fortentwickelt und liefert Lösungen für unterschiedliche Visualisierungen, die auf Graphen beruhen.

<div class="mw-heading mw-heading2"><h2 id="Erweiterungen">Erweiterungen</h2></div>

Graphen können mit weiteren Eigenschaften bzw. Informationen ergänzt werden.

<div class="mw-heading mw-heading3"><h3 id="Gefärbte_Graphen">Gefärbte Graphen</h3></div>

Eine Erweiterung von Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> zu <a href="Knotengef%C3%A4rbter_Graph" title="Knotengefärbter Graph">knotengefärbten Graphen</a> erhält man, indem das Tupel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01724c7d662052bd5f1c34cb725c8001634069a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.406ex; height:2.843ex;" alt="{\displaystyle (V,E)}" loading="lazy"> zu einem Tripel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E,f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V,E,f)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4ea716aafe02b37d31f72d789aeb6bb406c66723.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.719ex; height:2.843ex;" alt="{\displaystyle (V,E,f)}" loading="lazy"> ergänzt wird. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> ist eine Abbildung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> in die Menge der <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahlen</a>. Anschaulich gibt man jedem Knoten damit eine Farbe.

Statt der Knoten kann man in Graphen ohne Mehrfachkanten und in Hypergraphen auch die Kanten färben und spricht dann von einem <a href="Kantengef%C3%A4rbter_Graph" title="Kantengefärbter Graph">kantengefärbten Graphen</a>. Dazu erweitert man ebenfalls das Tupel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01724c7d662052bd5f1c34cb725c8001634069a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.406ex; height:2.843ex;" alt="{\displaystyle (V,E)}" loading="lazy"> zu einem Tripel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E,f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V,E,f)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4ea716aafe02b37d31f72d789aeb6bb406c66723.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.719ex; height:2.843ex;" alt="{\displaystyle (V,E,f)}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> aber eine Abbildung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> (statt von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy">) in die Menge der <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahlen</a> ist. Anschaulich gibt man jeder Kante damit eine Farbe. In Graphen mit Mehrfachkanten ist dies zwar prinzipiell auch möglich, aber schwieriger zu definieren, insbesondere, wenn Mehrfachkanten entsprechend ihrer Vielfachheit mehrere verschiedene Farben zugeordnet werden sollen.

Man beachte, dass die Begriffe „Färbung“ und „färben“ in der Graphentheorie auch eine speziellere Bedeutung besitzen. Exakt spricht man dann zwar von <a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">gültiger Färbung</a>, lässt das Attribut „gültig“ aber meist weg.

Analog gibt es auch benannte Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E,f,g)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V,E,f,g)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ff69090df7611feee7e4da0689d1886db400fc68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.869ex; height:2.843ex;" alt="{\displaystyle (V,E,f,g)}" loading="lazy">, bei denen Knoten und/oder Kanten einen Namen tragen, und die Abbildungen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> den Knoten bzw. Kanten einen Namen zuordnen. Die zuvor abgebildeten Beispiele sind benannte Graphen, bei denen die Knoten mit Buchstaben benannt wurden. Dies wird oft bei Visualisierungen gemacht, so dass man besser über den Graphen diskutieren kann.

<div class="mw-heading mw-heading3"><h3 id="Gewichtete_Graphen">Gewichtete Graphen</h3></div>

Statt von knoten- bzw. kantengefärbten Graphen spricht man von <a href="Knotengewichteter_Graph" title="Knotengewichteter Graph">knoten-</a> bzw. <a href="Kantengewichteter_Graph" title="Kantengewichteter Graph">kantengewichteten</a> Graphen, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> statt in die natürlichen Zahlen in die <a href="Reelle_Zahl" title="Reelle Zahl">reellen Zahlen</a> abbildet. Knoten- bzw. kantengefärbte Graphen sind also Spezialfälle von knoten- bzw. kantengewichteten Graphen.

Man bezeichnet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92b2b785b7b6d9a22484d466da88d6328ed0b197.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.215ex; height:2.843ex;" alt="{\displaystyle f(v)}" loading="lazy"> bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(e)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(e)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ff5e01076011aae0013a78dcee0fabbacc06a8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.171ex; height:2.843ex;" alt="{\displaystyle f(e)}" loading="lazy"> auch als Gewicht des Knotens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> bzw. der Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">. Zur Unterscheidung spricht man auch von Knotengewicht bzw. Kantengewicht. Eine solche Gewichtung wird erforderlich, wenn die Information über Knotenbeziehungen nicht ausreicht. Fasst man beispielsweise das Straßennetz (vereinfacht) als Graph auf (Orte sind Knoten, die Orte verbindende Straßen sind Kanten), so könnte eine Gewichtung der Kanten Aufschluss über die Distanz zwischen zwei Orten geben. Die Kantengewichte eines Graphen können in einer quadratischen Gewichtsmatrix, der <a href="Adjazenzmatrix" title="Adjazenzmatrix">Adjazenzmatrix</a>, gesammelt werden.

<div class="mw-heading mw-heading3"><h3 id="Abbildungen_zwischen_Graphen">Abbildungen zwischen Graphen</h3></div>

Schließlich lassen sich auch Abbildungen zwischen Graphen definieren. Interessant sind insbesondere solche, die mit der Struktur der beiden <a href="Vertr%C3%A4glichkeit_(Mathematik)" title="Verträglichkeit (Mathematik)">verträglich</a> sind, so genannte <a href="Homomorphismus" title="Homomorphismus">„Homomorphismen“</a>.

Seien dazu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=\left(V_{1},E_{1}\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=\left(V_{1},E_{1}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/62966e855289c331a2702d576eb0e58b3ce02cec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{1}=\left(V_{1},E_{1}\right)}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=\left(V_{2},E_{2}\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=\left(V_{2},E_{2}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c737ecc4a49e690b59ce882f0dde856e580d3666.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{2}=\left(V_{2},E_{2}\right)}" loading="lazy"> Graphen desselben Typs. Eine <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Abbildung</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\colon V_{1}\to V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\colon V_{1}\to V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d7b6853cbb7ebfbc0661014c344cb740d931639e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:10.726ex; height:2.509ex;" alt="{\displaystyle p\colon V_{1}\to V_{2}}" loading="lazy"> heißt Homomorphismus zwischen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">, falls gilt:

<ul><li>In <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteten</a> <a href="Graph_ohne_Mehrfachkanten" class="mw-redirect" title="Graph ohne Mehrfachkanten">Graphen ohne Mehrfachkanten</a>: Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v,w\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v,w\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/28e854ab4af953d89a5fb8b23691f8da3f8c0f1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.151ex; height:2.843ex;" alt="{\displaystyle \{v,w\}}" loading="lazy"> eine Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{p(v),p(w)\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{p(v),p(w)\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba8b266a95c57b43576ae2ca16a30bf7abcd4919.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.108ex; height:2.843ex;" alt="{\displaystyle \{p(v),p(w)\}}" loading="lazy"> eine Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">.</li>

<li>In <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten</a> Graphen ohne Mehrfachkanten: Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (v,w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (v,w)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe1ba70e3b2d314bc63be62afe1e5c3a80b95834.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.635ex; height:2.843ex;" alt="{\displaystyle (v,w)}" loading="lazy"> Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy">, dann ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p(v),p(w))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p(v),p(w))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eb044fd0fbf429eeaaf61964782c358d1f31423c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.592ex; height:2.843ex;" alt="{\displaystyle (p(v),p(w))}" loading="lazy"> Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">.</li>

<li>In ungerichteten <a href="Graph_mit_Mehrfachkanten" class="mw-redirect" title="Graph mit Mehrfachkanten">Graphen mit Mehrfachkanten</a>: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{1}(\{v,w\})\leq E_{2}(\{p(v),p(w)\})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}(\{v,w\})\leq E_{2}(\{p(v),p(w)\})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d800f7c202306f6d5d1b0b89d19ca2550290eae2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.515ex; height:2.843ex;" alt="{\displaystyle E_{1}(\{v,w\})\leq E_{2}(\{p(v),p(w)\})}" loading="lazy">, d. h. je zwei Ecken sind mit höchstens so vielen Kanten verbunden wie ihre Bildecken.</li>

<li>In gerichteten Graphen mit Mehrfachkanten: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{1}(v,w)\leq E_{2}(p(v),p(w))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}(v,w)\leq E_{2}(p(v),p(w))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac5a3df58084b089d18e65a7a7ab3cf91d525b5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.865ex; height:2.843ex;" alt="{\displaystyle E_{1}(v,w)\leq E_{2}(p(v),p(w))}" loading="lazy">.</li>

<li>In gerichteten Graphen mit eigenständigen Mehrfachkanten: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> hat einen dazugehörenden Partner <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\colon E_{1}\to E_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q\colon E_{1}\to E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c5f165ca405b65f3a41583a908e58d5a94c9aa80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.257ex; height:2.509ex;" alt="{\displaystyle q\colon E_{1}\to E_{2}}" loading="lazy"> und für alle Kanten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/19f7cd88c3267329b35b5fe4a9187d1fc6644e64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.694ex; height:2.509ex;" alt="{\displaystyle e\in E_{1}}" loading="lazy"> gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {src} _{2}(q(e))=p(\mathrm {src} _{1}(e))}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {src} _{2}(q(e))=p(\mathrm {src} _{1}(e))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6cf5a3d7f748ba958f2c7f8de0625b59a032142.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.571ex; height:2.843ex;" alt="{\displaystyle \mathrm {src} _{2}(q(e))=p(\mathrm {src} _{1}(e))}" loading="lazy"> sowie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {tgt} _{2}(q(e))=p(\mathrm {tgt} _{1}(e))}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {tgt} _{2}(q(e))=p(\mathrm {tgt} _{1}(e))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8691ce56ebae82f709f074d59e11ef5c64e0741.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.794ex; height:2.843ex;" alt="{\displaystyle \mathrm {tgt} _{2}(q(e))=p(\mathrm {tgt} _{1}(e))}" loading="lazy"> (werden <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"> als Funktoren angesehen, ist ein Graphhomomorphismus gerade eine <a href="Nat%C3%BCrliche_Transformation" title="Natürliche Transformation">natürliche Transformation</a>).</li>

<li>In <a href="Hypergraph" class="mw-redirect" title="Hypergraph">Hypergraphen</a>: Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v_{1},\cdots ,v_{k}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v_{1},\cdots ,v_{k}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/29b8d598ad98b280d2789f39526fdc4953a38599.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.901ex; height:2.843ex;" alt="{\displaystyle \{v_{1},\cdots ,v_{k}\}}" loading="lazy"> Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{p(v_{1}),\cdots ,p(v_{k})\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{p(v_{1}),\cdots ,p(v_{k})\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bcbffac47e6af11cd64406fae8badc5d0784a795.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.859ex; height:2.843ex;" alt="{\displaystyle \{p(v_{1}),\cdots ,p(v_{k})\}}" loading="lazy"> Kante von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">.</li></ul>

Das Bild p(G1) ist dann ein <a href="Teilgraph" title="Teilgraph">Teilgraph</a> von G2. Ist p <a href="Bijektivit%C3%A4t" class="mw-redirect" title="Bijektivität">umkehrbar</a> und die <a href="Umkehrfunktion" title="Umkehrfunktion">Umkehrfunktion</a> ebenfalls ein Homomorphismus, so ist p ein <a href="Isomorphie_von_Graphen" title="Isomorphie von Graphen">Isomorphismus</a> von Graphen.

Zu beachten ist, dass die Knoten vor den Kanten einen Vorrang haben, indem p als <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Funktion</a> nur auf den Knoten spezifiziert ist, die auf den Kanten lediglich eine induzierte Wirkung entfaltet.

<div class="mw-heading mw-heading2"><h2 id="Kombinatorik">Kombinatorik</h2></div>

Die Anzahl der <a href="Einfacher_Graph" title="Einfacher Graph">einfachen</a> ungerichteten Graphen mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> steigt rasant mit der Anzahl der Knoten und ist gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{\tfrac {n\cdot (n-1)}{2}}}">

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{\tfrac {n\cdot (n-1)}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/76f5fd520c15e2570500bd61c42052116423002e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.041ex; height:4.509ex;" alt="{\displaystyle 2^{\tfrac {n\cdot (n-1)}{2}}}" loading="lazy">. Sie steigt also <a href="Exponentieller_Verlauf" class="mw-redirect" title="Exponentieller Verlauf">exponentiell</a> zur Anzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {n\cdot (n-1)}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {n\cdot (n-1)}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43b9872b53ac14f8e745ac6528840e20af56f41d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.646ex; height:4.176ex;" alt="{\displaystyle {\tfrac {n\cdot (n-1)}{2}}}" loading="lazy"> der <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> des <a href="Vollst%C3%A4ndiger_Graph" title="Vollständiger Graph">vollständigen Graphen</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea2b988ea630d2c5571afe47efa3d3b251708acb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.192ex; height:2.509ex;" alt="{\displaystyle K_{n}}" loading="lazy">. Wenn die Knoten nicht nummeriert sind, <a href="Isomorphie_von_Graphen" title="Isomorphie von Graphen">isomorphe Graphen</a> also nicht mitgezählt werden, ist diese Anzahl etwa <a href="Proportionalit%C3%A4t" title="Proportionalität">proportional</a> zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d6987a46a1d96b208d6a99990283d01a19091230.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:11.999ex; height:5.509ex;" alt="{\displaystyle {\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}}" loading="lazy">, weil für die meisten <a href="Isomorphieklasse" class="mw-redirect" title="Isomorphieklasse">Isomorphieklassen</a> alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bae971720be3cc9b8d82f4cdac89cb89877514a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}" loading="lazy"> Graphen, die sich durch <a href="Permutation" title="Permutation">Permutation</a> der nummerierten Knoten ergeben, verschieden sind. Die folgende <a href="Tabelle" title="Tabelle">Tabelle</a> zeigt die mit Hilfe eines <a href="Computer" title="Computer">Computers</a> bestimmten Anzahlen für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\leq 8}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\leq 8}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d52855c222e6eacc0c626213394031fa37d5e4cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\leq 8}" loading="lazy">:<a href="#cite_note-6">[6]</a>

<th colspan="3">Anzahl der einfachen ungerichteten Graphen

</th></tr>

<tr>

<th>n

</th>

<th>mit nummerierten Knoten

</th>

<th>ohne nummerierte Knoten

</th></tr>

<tr>

<th>1

</th>

<td>1

</td>

<td>1

</td></tr>

<tr>

<th>2

</th>

<td>2

</td>

<td>2

</td></tr>

<tr>

<th>3

</th>

<td>8

</td>

<td>4

</td></tr>

<tr>

<th>4

</th>

<td>64

</td>

<td>11

</td></tr>

<tr>

<th>5

</th>

<td>1.024

</td>

<td>34

</td></tr>

<tr>

<th>6

</th>

<td>32.768

</td>

<td>156

</td></tr>

<tr>

<th>7

</th>

<td>2.097.152

</td>

<td>1.044

</td></tr>

<tr>

<th>8

</th>

<td>268.435.456

</td>

<td>12.346

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Datenstrukturen">Datenstrukturen</h2></div>

<th>Ungerichteter Graph

</th>

<th>Adjazenzmatrix

</th></tr>

<tr>

<td>

</td>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/baf5d604fec8ccaa37056a87411c0a7e3920730e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.005ex; width:23.406ex; height:19.176ex;" alt="{\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}" loading="lazy">

</td></tr></tbody></table>

Für die Repräsentation von Graphen im <a href="Computer" title="Computer">Computer</a> gibt es im Wesentlichen zwei gebräuchliche Formen: die <a href="Adjazenzmatrix" title="Adjazenzmatrix">Adjazenzmatrix</a> (auch Nachbarschaftsmatrix) und die <a href="Adjazenzliste" title="Adjazenzliste">Adjazenzliste</a> (Nachbarschaftsliste). Die Bedeutung der beiden Darstellungen liegt darin, dass praktisch jede algorithmische Lösung graphentheoretischer Probleme auf wenigstens eine der beiden Repräsentationen zurückgreift. Eine weitere, aber seltener genutzte Möglichkeit zur Darstellung von Graphen im Computer ist die <a href="Inzidenzmatrix" title="Inzidenzmatrix">Inzidenzmatrix</a>, die man auch als Knoten-Kanten-Matrix bezeichnet.

Inzidenzmatrizen sind zwar aufwändiger zu implementieren und zu verwalten, bieten aber eine Reihe von Vorteilen gegenüber Adjazenzmatrizen. Zum einen verbrauchen sie bei fester Anzahl von Kanten stets nur linear viel Speicherplatz bezüglich der Anzahl der Knoten, was insbesondere bei dünnen Graphen (also Graphen mit wenig Kanten) von Vorteil ist, während die Adjazenzmatrix quadratischen Platzbedarf bezüglich der Anzahl Knoten besitzt (dafür aber kompakter bei dichten Graphen, also Graphen mit vielen Kanten ist). Zum anderen lassen sich viele graphentheoretische Probleme nur mit Adjazenzlisten in <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">linearer Zeit</a> lösen. In der Praxis verwendet man daher meist diese Form der Repräsentation.

<div class="mw-heading mw-heading2"><h2 id="Programmierung">Programmierung</h2></div>

Das folgende Beispiel in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C%2B%2B" title="C++">C++</a> zeigt die <a href="Implementierung" title="Implementierung">Implementierung</a> eines <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten Graphen</a> mit <a href="Adjazenzliste" title="Adjazenzliste">Adjazenzlisten</a>. Der gerichtete Graph wird als <a href="Klasse_(Objektorientierung)" title="Klasse (Objektorientierung)">Klasse</a> DirectedGraph deklariert. Bei der Ausführung des Programms wird die <a href="Methode_(Programmierung)" title="Methode (Programmierung)">Methode</a> main verwendet.<a href="#cite_note-7">[7]</a>

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre>#include <iostream>

using namespace std;

// Deklariert den Datentyp für die Knoten des Graphen

struct Node

{

int index;

string value;

Node* next;

};

// Deklariert den Datentyp für die Kanten des Graphen

struct Edge

{

int startIndex;

int endIndex;

};

// Deklariert die Klasse für den gerichteten Graphen

class DirectedGraph

{

public:

Node* nodes;

Node** headNodes;

// Diese Methode fügt einen neuen Knoten in die Adjazenzliste des Graphen ein und gibt ihn als Rückgabewert zurück

Node* insertNewNode(int index, string value, Node* node)

{

Node* newNode = new Node; // Erzeugt einen neuen Knoten vom Typ Node

newNode->index = index; // Setzt den Index

newNode->value = value; // Setzt den Wert

newNode->next = node; // Setzt einen Zeiger auf den Nachfolger

return newNode;

}

// Konstruktor, der den gerichteten Graphen mit den gegebenen Knoten und Kanten erzeugt

DirectedGraph(Node mynodes[], Edge edges[], int numberOfEdges, int numberOfNodes)

{

nodes = mynodes; //speichert Knoten

headNodes = new Node*[numberOfNodes](); // Initialisiert ein Array von Zeigern für die Nachbarknoten

for (int i = 0; i < numberOfEdges; i++) // for-Schleife, die alle Kanten des Graphen durchläuft

{

int startIndex = edges[i].startIndex; // Index des Startknotens der Kante

int endIndex = edges[i].endIndex; // Index des Endknotens der Kante

string value = nodes[endIndex].value; // Wert des Endknotens der Kante

Node* newNode = insertNewNode(endIndex, value, headNodes[startIndex]); // Aufruf der Methode insertNewNode, um einen neuen Knoten einzufügen

headNodes[startIndex] = newNode; // Setzt den Zeiger auf den neuen Knoten

}

};

// Gibt alle benachbarten Knoten von node auf der Konsole aus

void writeAdjacencyList(Node* node, Node* neighbor)

{

cout << "Knoten (" << node->index << ", " << node->value << "): ";

while (neighbor != nullptr)

{

cout << "(" << neighbor->index << ", " << neighbor->value << ") ";

neighbor = neighbor->next;

}

cout << endl;

}

// Hauptmethode, die das Programm ausführt

int main()

{

// Deklariert und initialisiert Arrays für die Knoten und Kanten

Node nodes[] = { {0,"A"},{1,"B"},{2,"C"},{3,"D"},{4,"E"} };

Edge edges[] = { {0,1},{0,2},{1,4},{2,3},{3,1},{4,3} };

int numberOfNodes = sizeof(nodes) / sizeof(nodes[0]); // Ermittelt die Anzahl der Knoten

int numberOfEdges = sizeof(edges) / sizeof(edges[0]); // Ermittelt die Anzahl der Kanten

DirectedGraph directedGraph(nodes, edges, numberOfEdges, numberOfNodes); // Erzeugt den gerichteten Graphen mit den gegebenen Knoten und Kanten

for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten des Graphen durchläuft

{

Node* headNode = directedGraph.headNodes[i];

writeAdjacencyList(&nodes[i], headNode); // Gibt die Adjazenzliste für den Knoten node mit Nachbarn headNode aus

}

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Graphenspiele" title="Graphenspiele">Graphenspiele</a></li>

<li><a href="Kleine-Welt-Ph%C3%A4nomen" title="Kleine-Welt-Phänomen">Kleine-Welt-Phänomen</a> (Small-world-Netzwerk)</li>

<li><a href="Skalenfreies_Netz" title="Skalenfreies Netz">Skalenfreies Netz</a></li>

<li><a href="Zufallsgraph" title="Zufallsgraph">Zufallsgraph</a></li>

<li><a href="Bandgraph" title="Bandgraph">Bandgraph</a></li>

<li><a href="Mengensystem" title="Mengensystem">Mengensystem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Thomas H. Cormen, <a href="Charles_Leiserson" class="mw-redirect" title="Charles Leiserson">Charles Leiserson</a>, <a href="Ronald_L._Rivest" title="Ronald L. Rivest">Ronald L. Rivest</a>, Clifford Stein: <cite style="font-style:italic">Algorithmen – Eine Einführung</cite>. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, S. 531–533.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.au=Thomas+H.+Cormen%2C+Charles+Leiserson%2C+Ronald+L.+Rivest%2C+...&rft.btitle=Algorithmen+-+Eine+Einf%C3%BChrung&rft.date=2007&rft.edition=2.&rft.genre=book&rft.isbn=9783486582628&rft.pages=531-533&rft.place=M%C3%BCnchen&rft.pub=Oldenbourg+Wissenschaftsverlag" style="display:none"> </li>

<li><a href="Reinhard_Diestel" title="Reinhard Diestel">Reinhard Diestel</a>: <cite style="font-style:italic">Graphentheorie</cite>. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5 (<a rel="nofollow" class="external text" href="https://diestel-graph-theory.com/basic.html">online: 4th Electronic Edition 2010, Free preview version</a> – Erstausgabe: 1996).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.au=Reinhard+Diestel&rft.btitle=Graphentheorie&rft.date=2010&rft.edition=4.&rft.genre=book&rft.isbn=9783642149115&rft.place=Berlin+u.+a.&rft.pub=Springer" style="display:none"> </li>

<li>Jürgen Ebert: <cite style="font-style:italic">Effiziente Graphenalgorithmen</cite>. In: <cite style="font-style:italic">Studien-Texte – Informatik</cite>. Akademische Verlags-Gesellschaft, Wiesbaden 1981, ISBN 3-400-00424-3 (Zugleich <a href="Habilitationsschrift" title="Habilitationsschrift">Habilitationsschrift</a> an der <a href="Universit%C3%A4t_Osnabr%C3%BCck" title="Universität Osnabrück">Universität Osnabrück</a> 1982).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.atitle=Effiziente+Graphenalgorithmen&rft.au=J%C3%BCrgen+Ebert&rft.btitle=Studien-Texte+-+Informatik&rft.date=1981&rft.genre=book&rft.isbn=3400004243&rft.place=Wiesbaden&rft.pub=Akademische+Verlags-Gesellschaft" style="display:none"> </li>

<li><a href="Dieter_Jungnickel" title="Dieter Jungnickel">Dieter Jungnickel</a>: <cite style="font-style:italic">Graphen, Netzwerke und Algorithmen</cite>. 3. vollständig überarbeitete und erweiterte Auflage. BI-Wissenschafts-Verlag, Mannheim u. a. 1994, ISBN 3-411-14263-4 (<a rel="nofollow" class="external text" href="https://www.gbv.de/dms/ilmenau/toc/164094962.PDF">Inhaltsverzeichnis</a> [PDF; 1,2 MB]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.au=Dieter+Jungnickel&rft.btitle=Graphen%2C+Netzwerke+und+Algorithmen&rft.date=1994&rft.edition=3.+vollst%C3%A4ndig+%C3%BCberarbeitete+und+erweiterte&rft.genre=book&rft.isbn=3411142634&rft.place=Mannheim+u.+a.&rft.pub=BI-Wissenschafts-Verlag" style="display:none"> </li>

<li>Manfred Nitzsche: <cite style="font-style:italic">Graphen für Einsteiger. Rund um das <a href="Haus_vom_Nikolaus" title="Haus vom Nikolaus">Haus vom Nikolaus</a></cite>. In: <cite style="font-style:italic">Studium</cite>. 3., überarbeitete und erweiterte Auflage. Vieweg+Teubner, Wiesbaden 2009, ISBN 978-3-8348-0813-4.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.atitle=Graphen+f%C3%BCr+Einsteiger.+Rund+um+das+Haus+vom+Nikolaus&rft.au=Manfred+Nitzsche&rft.btitle=Studium&rft.date=2009&rft.edition=3.%2C+%C3%BCberarbeitete+und+erweiterte&rft.genre=book&rft.isbn=9783834808134&rft.place=Wiesbaden&rft.pub=Vieweg%2BTeubner" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-Diestel2010-1">↑ <a href="#cite_ref-Diestel2010_1-0">a</a> <a href="#cite_ref-Diestel2010_1-1">b</a> <a href="#cite_ref-Diestel2010_1-2">c</a> <a href="#cite_ref-Diestel2010_1-3">d</a> <a href="Reinhard_Diestel" title="Reinhard Diestel">Reinhard Diestel</a>: <cite style="font-style:italic">Graphentheorie</cite>. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5, S. 1–34 (<a rel="nofollow" class="external text" href="https://diestel-graph-theory.com/basic.html">online: 4th elektronische Ausgabe 2010</a> – Erstausgabe: 1996).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.au=Reinhard+Diestel&rft.btitle=Graphentheorie&rft.date=2010&rft.edition=4.&rft.genre=book&rft.isbn=9783642149115&rft.pages=1-34&rft.place=Berlin+u.+a.&rft.pub=Springer" style="display:none">

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> <cite style="font-style:italic">Directed Graphs</cite>. In: Claude Sammut, Geoffrey I. Webb (Hrsg.): <cite style="font-style:italic">Encyclopedia of Machine Learning</cite>. Springer US, 2010, S. 279, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-0-387-30164-8_218">10.1007/978-0-387-30164-8_218</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.atitle=Directed+Graphs&rft.btitle=Encyclopedia+of+Machine+Learning&rft.date=2010&rft.doi=10.1007%2F978-0-387-30164-8_218&rft.genre=book&rft.pages=279&rft.pub=Springer+US" style="display:none">

</li>

<li id="cite_note-MultDirected-3"><a href="#cite_ref-MultDirected_3-0">↑</a> bei gerichteten Graphen: in derselben Richtung

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Stephen Wolfram: <a rel="nofollow" class="external text" href="https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/?dateline=no">Finally We May Have a Path to the Fundamental Theory of Physics… and It’s Beautiful</a> abgerufen am 20. Januar 2024.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> Brigitte Werners: <cite style="font-style:italic">Grundlagen des Operations Research</cite>. 3. Auflage. Springer, Berlin Heidelberg 2013, ISBN 978-3-642-40101-5, S. 175–209.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Graph+%28Graphentheorie%29&rft.au=Brigitte+Werners&rft.btitle=Grundlagen+des+Operations+Research&rft.date=2013&rft.edition=3&rft.genre=book&rft.isbn=9783642401015&rft.pages=175-209&rft.place=Berlin+Heidelberg&rft.pub=Springer" style="display:none">

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Folge <a href="https://oeis.org/A000088" class="extiw external" title="oeis:A000088">A000088</a> in <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> Software Testing Help: <a rel="nofollow" class="external text" href="https://www.softwaretestinghelp.com/graph-implementation-cpp/">Graph Implementation In C++ Using Adjacency List</a>

</li>

</ol>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4021842-9">4021842-9</a> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-09-27" href="https://de.wikipedia.org/wiki/?title=Graph_(Graphentheorie)&oldid=260114694">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>